package offer2

import (
	"container/heap"
)

/**
原题链接:
https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/

B站小美算法讲解
剑指 Offer 41. 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，
	[2,3,4] 的中位数是 3
	[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：
	void addNum(int num): 从数据流中添加一个整数到数据结构中。
	double findMedian():  返回目前所有元素的中位数。

示例 1：
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
*/

/**
思路:
1.查找中位数操作:
	找中位数,考虑使用堆
	需要维护两个堆,一个是大根堆,一个是小根堆
	让大根堆保存较小的那一部分数,  让小根堆保存较大的那一部分数,
	那么中位数就是两个堆分别弹出堆顶元素, (大顶堆元素 + 小顶堆元素)/2即可

	如果元素个数为偶数:  两个堆保存的数字的个数都是 n/2
	如果元素个数为奇数:  规定大根堆多保存一个,并且找中位数直接弹出大根堆堆顶元素即可

2.插入元素操作:
	如果当前元素个数为偶数: 把元素添加到小根堆中,然后再把小根堆的堆顶元素,移动到大根堆中
	如果当前元素个数为奇数: 同样需要先放入大根堆, 然后将大根堆堆顶元素, 移动到小根堆中
	目的是如果元素个数为奇数, 维持小根堆多存储一个元素
		如果元素个数为偶数, 维持两个堆存储元素个数相等   这样方便计算中位数
*/

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

type MedianFinder struct {
	maxHeap *MaxHeap
	minHeap *MinHeap
}

func Constructor() MedianFinder {
	maxHeap := &MaxHeap{}
	minHeap := &MinHeap{}
	heap.Init(maxHeap)
	heap.Init(minHeap)
	return MedianFinder{
		maxHeap: maxHeap,
		minHeap: minHeap,
	}
}

func (this *MedianFinder) AddNum(num int) {
	if this.maxHeap.Len() == this.minHeap.Len() {
		heap.Push(this.maxHeap, num)
	} else {
		heap.Push(this.minHeap, num)
	}

	if this.minHeap.Len() > 0 && (*this.minHeap)[0] < (*this.maxHeap)[0] {
		max := heap.Pop(this.maxHeap).(int)
		min := heap.Pop(this.minHeap).(int)
		heap.Push(this.maxHeap, min)
		heap.Push(this.minHeap, max)
	}
}

func (this *MedianFinder) FindMedian() float64 {
	if this.maxHeap.Len() == this.minHeap.Len() {
		return float64((*this.maxHeap)[0]+(*this.minHeap)[0]) / 2.0
	} else {
		return float64((*this.maxHeap)[0])
	}
}
